'''
https://leetcode.cn/problems/interleaving-string/description/
interleaving: 交错,交叉
'''
from functools import cache


class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False

        # s1[0,i] 与 s2[0,j]已经组成s3的[0, i+j-1]
        @cache
        def f(i, j):
            if i == m:
                return s2[j:] == s3[m + j:]
            if j == n:
                return s1[i:] == s3[i + n:]
            return (s1[i] == s3[i + j] and f(i + 1, j)) or (s2[j] == s3[i + j] and f(i, j + 1))

        return f(0, 0)

    # dp 打表
    def isInterleave2(self, s1: str, s2: str, s3: str) -> bool:
        m, n = len(s1), len(s2)
        if m + n != len(s3):
            return False
        # 依赖右边和下边
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        for i in range(m, -1, -1):
            # j == n, 可以写为逐字符比较，可以直接break
            dp[i][n] = s1[i:] == s3[i + n:]
        for j in range(n, -1, -1):
            # i == m
            dp[m][j] = s2[j:] == s3[m + j:]
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                dp[i][j] = (s1[i] == s3[i + j] and dp[i + 1][j]) or (s2[j] == s3[i + j] and dp[i][j + 1])
        return dp[0][0]

    # 空间压缩
    pass

